use rand::Rng;

fn bmul(mut a: u128, mut b: u128, m: u128) -> u128 {
    // 快速乘
    a %= m;
    let mut res = 0;
    while b > 0 {
        if (b & 1) == 1 {
            res = (res + a) % m;
        }
        a = (a << 1) % m;
        b >>= 1;
    }
    res
}

fn qpow(mut x: u128, mut p: u128, m: u128) -> u128 {
    // 快速幂
    let mut ans = 1;
    while p != 0 {
        if (p & 1) == 1 {
            ans = bmul(ans, x, m);
        }
        x = bmul(x, x, m);
        p >>= 1;
    }
    ans
}

fn miller_rabin(p: u128) -> bool {
    // 判断素数
    if p < 2 {
        return false;
    }
    if p == 2 {
        return true;
    }
    if p == 3 {
        return true;
    }
    if p % 6 != 1 && p % 6 != 5 {
        return false;
    }
    let mut d = p - 1;
    let mut r = 0;
    while (d & 1) == 0 {
        r += 1;
        d >>= 1; // 将d处理为奇数
    }
    let mut rng = rand::thread_rng();

    for _ in 0..10 {
        let a = rng.gen::<u128>() % (p - 2) + 2;
        let mut x = qpow(a, d, p);
        if x == 1 || x == p - 1 {
            continue;
        }
        for _ in 0..r {
            x = bmul(x, x, p);
            if x == p - 1 {
                break;
            }
        }
        if x != p - 1 {
            return false;
        }
    }
    true
}

fn side_count(side: u128) -> u32 {
    // n(n - 1) + 1
    // n(n - 2) + 2
    // n(n - 3) + 3

    // n ^ 2 - n + 1
    // n ^ 2 - 2n + 2
    // n ^ 2 - 3n + 3
    let end = side * side;
    let mut prime_count = 0;
    if miller_rabin(end - (side << 1) + 2) {
        prime_count += 1;
    }
    if miller_rabin(end - side * 3 + 3) {
        prime_count += 1;
    }
    if miller_rabin(end - side + 1) {
        prime_count += 1;
    }
    prime_count
}

// use std::{collections::HashMap, sync::mpsc::Sender, thread};
// use std::sync::mpsc::channel;

// fn start(side_start: u128, step: u128, tx: Sender<(u128, u32)>) {
//     thread::spawn(move || {
//         let mut side = side_start;
//         loop {
//             let _ = tx.send((side, side_count(side)));
//             side += step;
//         }
//     });
// }

// pub fn min_edge_prime_num_thread(number: u32) -> String {
//     let need_ratio = number as f64 / 100f64;
//     let (side, mut prime_count) = init(need_ratio);
//     let (tx, rx) = channel();
//     let thread_num = 32;
//     for n in 0..thread_num {
//         start(side + 2 * n, thread_num * 2, tx.clone());
//     }

//     let mut ok_side = side;
//     let mut cache = HashMap::new();
//     let mut next_c = 5000;
//     loop {
//         let need_side = ok_side + 2;
//         if let Some(v) = cache.remove(&need_side) {
//             prime_count += v;
//             ok_side = need_side;
//         } else {
//             while let Ok((s, v)) = rx.recv() {
//                 if s == need_side {
//                     prime_count += v;
//                     ok_side = need_side;
//                     break;
//                 } else {
//                     cache.insert(s, v);
//                 }
//             }
//         }
//         if prime_count >= next_c {
//             next_c += 5000;
//             println!("({ok_side}, {prime_count}),");
//         }
//         if prime_count as f64 / (((ok_side << 1) - 1) as f64) < need_ratio {
//             return format!("{},{}", ok_side, prime_count);
//         }
//     }
// }

const TABLE: [(u128, u32); 60] = [
    (24761, 5000),
    (53769, 10000),
    (84681, 15000),
    (116899, 20000),
    (149589, 25000),
    (183261, 30000),
    (216581, 35000),
    (251269, 40000),
    (285627, 45000),
    (320645, 50000),
    (355997, 55000),
    (391417, 60001),
    (427301, 65000),
    (463111, 70000),
    (499441, 75000),
    (535675, 80000),
    (571595, 85000),
    (608551, 90000),
    (645165, 95000),
    (681745, 100000),
    (718745, 105000),
    (756005, 110000),
    (793365, 115000),
    (831321, 120000),
    (868367, 125000),
    (906235, 130000),
    (944443, 135000),
    (982781, 140000),
    (1021441, 145000),
    (1060051, 150000),
    (1098447, 155000),
    (1137501, 160000),
    (1175891, 165000),
    (1214305, 170000),
    (1252465, 175000),
    (1291277, 180000),
    (1330625, 185000),
    (1370587, 190000),
    (1409479, 195000),
    (1448637, 200000),
    (1487825, 205000),
    (1527401, 210000),
    (1566787, 215000),
    (1606907, 220000),
    (1646065, 225000),
    (1686177, 230000),
    (1725491, 235000),
    (1765235, 240000),
    (1805247, 245000),
    (1845613, 250000),
    (1885327, 255000),
    (1925061, 260000),
    (1964905, 265000),
    (2004941, 270000),
    (2045265, 275000),
    (2085259, 280000),
    (2125363, 285000),
    (2165867, 290000),
    (2206465, 295000),
    (2246981, 300000),
];

fn init(need_ratio: f64) -> (u128, u32) {
    let mut side = 3;
    let mut prime_count = 3;
    for (s, p) in TABLE {
        if p as f64 / (((s << 1) - 1) as f64) <= need_ratio {
            break;
        }
        side = s;
        prime_count = p;
    }
    (side, prime_count)
}

pub fn min_edge_prime_num(number: u32) -> String {
    let need_ratio = number as f64 / 100f64;
    let (mut side, mut prime_count) = init(need_ratio);
    loop {
        side += 2;
        prime_count += side_count(side);
        if prime_count as f64 / (((side << 1) - 1) as f64) < need_ratio {
            return format!("{},{}", side, prime_count);
        }
    }
}
